/*Quick Sort Algorithm*/
#include<stdio.h>
#include<string.h>
#include<time.h>
#define ARRAYSIZE 	6	
#define FALSE		0
#define TRUE 		1

void quick_sort(int arr[], int beg, int end, int* steps) 
{
	int temp;
	if (end > beg){
		int piv = arr[beg], l = beg + 1, r = end;
		while (l < r){
			*steps++;
			if (arr[l] <= piv){
				l++;
			} else if(arr[r] >= piv){
				r--;
			} else {
				temp = arr[l];
				arr[l] = arr[r];
				arr[r] = temp;
			}
		}
		if(arr[l] < piv){
			*steps++;
			temp = arr[l];
			arr[l] = arr[beg];
			arr[beg] = temp;
			l--;
		} 
		else{
			*steps++;
			l--;
			temp = arr[l];
			arr[l] = arr[beg];
			arr[beg] = temp;
		}
		qsort(arr, beg, l);
		qsort(arr, r, end);
	}
	print_array(s);
}


void print_array(int a[])
{
	int i;
       	for(i=0;i<ARRAYSIZE;i++){
	       printf("- %d -", a[i]);
	}
	printf("\n");
}
void quick_sort_2(int s[], int first, int last, int* steps){
	int i, j, tmp2, pivote;
	tmp2 = (first + last)/2;
	pivote = s[tmp2];
	i = first;
	j = last;

	do {
		while (s[i] < pivote){
			i++;
			(*steps)++;
		}
		while (s[j] > pivote){ 
			j--;
			(*steps)++;
		}
		if (i<=j){
			tmp2 = s[i];
			s[i] = s[j];
			s[j] = tmp2;
			i++;
			j--;
		}
	} while (i<=j);
	if (first<j){
		quick_sort(s,first,i, steps);
	}
	if (i<last){
		quick_sort(s,j,last, steps);
	}
//	print_array(s);
//	printf("Steps = %d\n",steps);
}
	
int main() 
{
	int s[ARRAYSIZE];
	int i,cont = TRUE, t = 0;
	int steps=0;
	
	srand(time(0));
	for(i=0;i<ARRAYSIZE;i++){
		s[i] = random() % 1000;
	}
	print_array(s);
	printf("\n");
	quick_sort(s,t, ARRAYSIZE, &steps); 
	print_array(s);
	printf("Steps = %d\n",steps);
	return 1;	
}		
